|
This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are hundreds of such problems known, this list is in no way comprehensive. Many problems of this type can be found in . ==Graphs and hypergraphs== Graphs occur frequently in everyday applications. Examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (see e.g. Facebook or LinkedIn). *1-planarity *3-dimensional matching〔〔: SP1〕 *Bipartite dimension〔: GT18〕 *Capacitated minimum spanning tree〔: ND5〕 *Route inspection problem (also called Chinese postman problem) for mixed graphs (having both directed and undirected edges). The program is solvable in polynomial time if the graph has all undirected or all directed edges. Variants include the rural postman problem.〔: ND25, ND27〕 *Clique problem〔〔: GT19〕 *Complete coloring, a.k.a. achromatic number〔: GT5〕 *Domatic number〔: GT3〕 *Dominating set, a.k.a. domination number〔: GT2〕 ::NP-complete special cases include the edge dominating set problem, i.e., the dominating set problem in line graphs. NP-complete variants include the connected dominating set problem and the maximum leaf spanning tree problem.〔: ND2〕 *Bandwidth problem〔: GT40〕 *Clique cover problem〔〔: GT17〕 *Rank coloring a.k.a. cycle rank *Degree-constrained spanning tree〔: ND1〕 *Exact cover problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets (this is a matching).〔〔: SP2〕 *Feedback vertex set〔〔: GT7〕 *Feedback arc set〔〔: GT8〕 *Graph homomorphism problem〔: GT52〕 *Graph coloring〔〔: GT4〕 *Graph partition into subgraphs of specific types (triangles, isomorphic subgraphs, Hamiltonian subgraphs, forests, perfect matchings) are known NP-complete. Partition into cliques is the same problem as coloring the complement of the given graph. A related problem is to find a partition that is optimal terms of the number of edges between parts.〔: GT11, GT12, GT13, GT14, GT15, GT16, ND14〕 *Hamiltonian completion〔: GT34〕 *Hamiltonian path problem, directed and undirected.〔〔: GT37, GT38, GT39〕 *Longest path problem〔: ND29〕 *Maximum bipartite subgraph or (especially with weighted edges) maximum cut.〔〔: GT25, ND16〕 *Maximum independent set〔: GT20〕 *Maximum Induced path〔: GT23〕 *Graph intersection number〔: GT59〕 *Metric dimension of a graph〔: GT61〕 *Minimum k-cut *Minimum spanning tree, or Steiner tree, for a subset of the vertices of a graph.〔 (The minimum spanning tree for an entire graph is solvable in polynomial time.) *Pathwidth〔 *Set cover (also called minimum cover problem) This is equivalent, by transposing the incidence matrix, to the hitting set problem.〔〔: SP5, SP8〕 *Set splitting problem 〔: SP4〕 *Shortest total path length spanning tree〔: ND3〕 *Slope number two testing *Treewidth *Vertex cover〔: GT1〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「List of NP-complete problems」の詳細全文を読む スポンサード リンク
|